package cn.edu.xjtu.work.containsDuplicate;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * 217. 存在重复元素
 * 
 * 给定一个整数数组，判断是否存在重复元素。 如果存在一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。
 * 
 * 
 */
public class Solution {
  public static void main(String[] args) {
    int[] nums = new int[] { 1, 2, 3, 1 };
    System.out.println(containsDuplicate(nums));
  }

  /**
   * 排序
   * 
   * @param nums
   * @return
   */
  public static boolean containsDuplicate(int[] nums) {
    Arrays.sort(nums);
    for (int i = 0; i < nums.length - 1; i++) {
      if (nums[i] == nums[i + 1]) {
        return true;
      }
    }
    return false;
  }

  /**
   * 哈希表
   * 
   * @param nums
   * @return
   */
  public static boolean containsDuplicate1(int[] nums) {
    Set<Integer> set = new HashSet<>();
    for (int i : nums) {
      if (set.contains(i)) {
        return true;
      } else {
        set.add(i);
      }
    }
    return false;
  }
}
